package com.minigame.leetCode;

import java.util.Arrays;

/**
 * 给定一个数 n ，返回其 1-n 所有可能的全排列 。你可以 按任意顺序 返回答案。
 *
 * 示例 ：
 * 输入：n = 3
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 *
 */
public class Permutations {
    public static void main(String[] args) {
        int[][] permutations = permutations(5);
        for (int[] permutation : permutations) {
            System.out.println(Arrays.toString(permutation));
        }
    }
    public static int[][] permutations(int n) {
        if (n < 1) {
            return new int[0][];
        }
        int[][][] table = new int[n+1][][];
        //table[0] 不管, table[1] 为边界, 遍历从 table[2] 开始
        table[1] = new int[1][1];
        table[1][0] = new int[]{1};
        for (int i = 2; i < n + 1; i++) {
            table[i] = new int[table[i - 1].length * i][];
            //状态方程
            stateFunction(i, table[i - 1], table[i]);
        }
        return table[n];
    }

    public static void stateFunction(int n, int[][] left, int[][] current) {
        for (int i = 0; i < left.length; i++) {
            for (int j = n - 1; j >= 0; j--) {
                int index = n * i + n -1 - j;
                current[index] = new int[n];
                System.arraycopy(left[i], 0, current[index], 0, j);
                current[index][j] = n;
                System.arraycopy(left[i], j, current[index], j + 1, n - 1 - j);
            }
        }
    }
}
